package com.lw.leetcode.binary.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * c
 * binay
 * 2009. 使数组连续的最少操作数
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/1 9:53
 */
public class MinOperations {

    public static void main(String[] args) {
        MinOperations test = new MinOperations();

        // 0
//        int[] nums = {4, 2, 5, 3};

        // 1
//        int[] nums = {1, 2, 3, 5, 6};

        // 3
//        int[] nums = {1, 10, 100, 1000};

        // 3
        int[] nums = Utils.getArr(100000, 1, 1000000000, "C:\\lw\\myword\\a.txt");

        int i = test.minOperations(nums);
        System.out.println(i);
    }

    public int minOperations(int[] nums) {
        Arrays.sort(nums);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int length = nums.length;
        int item = nums[0];
        int count = 0;
        for (int i = 1; i < length; i++) {
            if (nums[i] == item) {
                count++;
            } else {
                map.put(item, count);
                item = nums[i];
            }
        }
        map.put(item, count);
        map.put(0, 0);
        int min = Integer.MAX_VALUE;
        int last = nums[length - 1];
        int pre = 0;
        for (int i = 0; i < length; i++) {
            int n = nums[i];
            if (n == pre) {
                continue;
            }
            pre = n;
            int t = n + length;
            int j = length - 1;
            if (t <= last) {
                j = find(nums, i, t);
            }
            int v = i + length - j - 1 - map.floorEntry(n - 1).getValue() + map.floorEntry(t).getValue();
            min = Math.min(min, v);
        }
        return min;
    }

    private int find(int[] nums, int st, int t) {
        int end = nums.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] >= t) {
                end = m - 1;

            } else {
                st = m;
            }
        }
        return st;
    }

}
